1. Field of the Invention
The invention relates to data compression and decompression.
2. Description of the Prior Art
LZW is a ubiquitously popular process for compressing and decompressing data and is utilized, for example, in such applications as the CCITT V.42 bis standard for modem communication. LZW is described in U.S. Pat. No. 4,558,302, issued Dec. 10, 1985 to Terry A. Welch, entitled "High Speed Data Compression And Decompression Apparatus And Method". Said U.S. Pat. No. 4,558,302 is incorporated herein by reference and is assigned to the assignee of the present invention.
LZW data compression utilizes a dictionary for storing strings of data characters encountered in the input and searching the input stream by comparing the input stream to the strings stored in the dictionary to determine the longest match therewith. The dictionary is augmented by storing an extended string comprising the longest match extended by the next input data character following the longest match. Traditionally, the data compression dictionary is implemented by Random Access Memory (RAM) storage. Welch suggests in said U.S. Pat. No. 4,558,302 (column 52, lines 30--34) that a content-addressable or associative memory might be utilized instead of the RAM which would reduce control complexity. Welch, however, did not describe in any way how this might be accomplished. It is believed that heretofore in the prior art an associative memory embodiment of the LZW compression algorithm has not been provided.
On the other hand, U.S. Pat. No. 4,366,551, issued Dec. 28, 1982 to Klaus E. Holtz, entitled "Associative Memory Search System", discloses a storage and searching system utilizing an associative memory. Said U.S. Pat. No. 4,366,551, however, does not disclose or suggest an associative memory embodiment of the LZW algorithm. Said U.S. Pat. No. 4,366,551 was cited and overcome in a re-examination of said U.S. Pat. No. 4,558,302, under re-examination certificate B 4,558,302, issued Jan. 4, 1994.